package lc2;

import java.util.*;
import org.junit.*;
import util.*;

public class Ex652 {
    class Solution1 {
        private List<TreeNode> res;
        private Map<Integer, List<TreeNode>> map;

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            res = new ArrayList<>();
            map = new HashMap<>();
            preOrder(root);
            for (int k : map.keySet()) {
                List<TreeNode> cur = map.get(k);
                if (cur.size() < 2) {
                    continue;
                }
                for (int i = 0; i < cur.size(); i++) {
                    for (int j = i + 1; j < cur.size(); j++) {
                        if (isSame(cur.get(i), cur.get(j))) {
                            res.add(cur.get(i));
                        }
                    }
                }
            }
            return res;
        }

        private void preOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            if (!map.containsKey(root.val)) {
                map.put(root.val, new ArrayList<>());
            }
            map.get(root.val).add(root);
            preOrder(root.left);
            preOrder(root.right);
        }

        private boolean isSame(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            } else if (p == null || q == null) {
                return false;
            }
            return p.val == q.val && isSame(p.left, q.left) && isSame(p.right, q.right);
        }
    }

    class Solution {
        private Map<String, List<TreeNode>> map;

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            List<TreeNode> res = new ArrayList<>();
            map = new HashMap<>();
            postOrder(root);
            for (String k : map.keySet()) {
                List<TreeNode> cur = map.get(k);
                if (cur.size() >= 2) {
                    res.add(cur.get(0));
                }
            }
            return res;
        }

        private String postOrder(TreeNode root) {
            if (root == null) {
                return "#";
            }
            String lStr = postOrder(root.left), rStr = postOrder(root.right);
            String cur = root.val + "_" + lStr + "_" + rStr;
            if (!map.containsKey(cur)) {
                map.put(cur, new ArrayList<>());
            }
            map.get(cur).add(root);
            return cur;
        }

    }

    @Test
    public void test() {
        Solution s = new Solution();
        Integer[] nums = new Integer[] { 2, 1, 11, 11, null, 1 };
        TreeNode root = TreeUtils.createTree(nums);
        List<TreeNode> res = s.findDuplicateSubtrees(root);
        System.out.println(res);
    }

    @Test
    public void test2() {
        // System.out.println(1000 / 15 * 500);
        // double t = Math.log(Math.E) - Math.log(Math.E * Math.E);
        // System.out.println(t);
        // System.out.println(getGuessTimes(10, 20, 11));
        System.out.println(Math.log1p(2));
        System.out.println(Math.log(20 - 10) - Math.log(2));
    }

    public int getGuessTimes(int min, int max, int number) {
        return (int) (Math.log(max - min + 1) - Math.log(2) + 1);
    }

    public int swapOddEven(int[] nums) {
        int n = nums.length;
        int lo = -1, hi = n, i = 0;
        while (i < hi) {
            if ((nums[i] & 1) == 1) {
                swap(nums, ++lo, i++);
            } else {
                swap(nums, --hi, i);
            }
        }
        return hi;
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    @Test
    public void test3() {
        int[] nums = new int[]{1,2,3};
        System.out.println(swapOddEven(nums));
    }

}
